import { preOrder } from "@/sources/Tree/BSTree/morris";

/**
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * 构造二叉树
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 * @param preorder
 * @param inorder
 */
const buildTree = (preorder: number[], inorder: number[]): TreeNode | null => {
  // 将中序遍历使用map映射
  // 属性是值, 值是索引
  const map: Record<number, number> = {};
  const inOrderLen = inorder.length;
  for (let i = 0; i < inOrderLen; i++) {
    map[inorder[i]] = i;
  }

  // 构建二叉树
  return build(preorder, inorder, 0, preorder.length - 1, 0, inOrderLen - 1, map);
};


 /**
   * 构造二叉树
   * @param preorder
   * @param inorder
   * @param preStart
   * @param preEnd
   * @param inStart
   * @param inEnd
   */
  const build = (
    preorder: number[], // 前序遍历数组
    inorder: number[], // 中序遍历数组
    preStart: number, // 前序遍历的开始
    preEnd: number, // 前序遍历的结束
    inStart: number, // 中序遍历的开始
    inEnd: number, // 中序遍历的结束
    map: Record<number, number> // 中序对应的map
  ): TreeNode | null => {
    // 超过了边界, 返回空
    if (preStart > preEnd) return null;

    // 获取根的索引
    const rootIndex = map[preorder[preStart]];

    // 左孩子的数量
    const leftCount = rootIndex - inStart;

    // 创建根
    const root = new TreeNode(preorder[preStart])

    // 构建左孩子
    root.left = build(preorder, inorder, preStart + 1, preStart + leftCount, inStart, rootIndex - 1, map)
    
    // 构建右孩子
    root.right = build(preorder, inorder, preStart + leftCount + 1, preEnd, rootIndex + 1, inEnd, map)

    return root;
  };
